package demo3;

//牛客网:城市群的数量
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param m int整型ArrayList<ArrayList<>> 
     * @return int整型
     */
     int n, m;
     boolean[] st;
    public int citys (ArrayList<ArrayList<Integer>> map) {
        // write code here
        n = map.size();
        st = new boolean[n];

        int count = 0;
        for(int i = 0; i<n; i++) {
            if(!st[i]) {
                count++;
                dfs(i,map);
            }
        }
       
        return count;
    }
   
    public void dfs(int x, ArrayList<ArrayList<Integer>> map) {
        for(int i = 0; i<n; i++) {
            if(map.get(x).get(i) == 1 && !st[i]) {
                st[i] = true;
                dfs(i,map);
            }
        }   
    }
}

/*
  1 2 3 4
1 1 1 0 0
2 1 1 1 0
3 0 1 1 0
4 0 0 0 1

1 2 3 

*/